#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <cmath>
#include <algorithm>
# include "force.h"

using namespace std;

struct Point {
    int x;
    int y;
};

// 计算两点之间的斜率
double calculateSlope(const Point& a, const Point& b) {
    if (a.x == b.x) {
        return INFINITY; // 无穷大，垂直线段
    }
    return static_cast<double>(b.y - a.y) / (b.x - a.x);
}

// 检查点c是否在ab线段的左侧
bool isLeftTurn(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) > 0;
}

// 使用斜率方法解决凸包问题
vector<Point> convexHullBySlope(vector<Point>& points) {
    int n = points.size();
    vector<Point> convexHull;

    for (int i = 0; i < n; i++) {
        cout<<i<<endl;
        Point a = points[i];
        bool onLeft = false, onRight = false;

        for (int j = 0; j < n; j++) {
            if (i != j) {
                Point b = points[j];
                double slope = calculateSlope(a, b);

                // 处理垂直线段
                if (slope == INFINITY) {
                    if (a.x < b.x) {
                        onRight = true;
                    } else {
                        onLeft = true;
                    }
                } else {
                    bool allOnLeft = true, allOnRight = true;

                    for (int k = 0; k < n; k++) {
                        if (k != i && k != j) {
                            Point c = points[k];
                            double crossProduct = (c.y - a.y) * (b.x - a.x) - (b.y - a.y) * (c.x - a.x);

                            if (crossProduct > 0) {
                                allOnRight = false;
                            } else if (crossProduct < 0) {
                                allOnLeft = false;
                            }
                        }
                    }

                    if (allOnLeft || allOnRight) {
                        onLeft |= allOnLeft;
                        onRight |= allOnRight;
                    }
                }
            }
        }

        if (onLeft && onRight) {
            convexHull.push_back(a);
        }
    }

    return convexHull;
}


